package lc.Q200_250;

import java.util.*;

public class Q210_2 {

    public static void main(String[] args) {
        Q210_2 q210 = new Q210_2();
        int[] order = q210.findOrder(2, new int[][]{
                new int[]{0, 1},
                new int[]{1, 0},
        });
        System.out.println(Arrays.toString(order));
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 首先构建图的边
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        // 广度优先,标记每个节点的度，表示有多少个前置节点
        int[] visited = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
            visited[prerequisite[0]] ++;
        }
        Deque<Integer> deque = new LinkedList<>();
        // 所有度为0的放队列
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                deque.addFirst(i);
            }
        }
        int[] result = new int[numCourses];
        int cur = 0;
        while (!deque.isEmpty()) {
            // 出队，如果度是0
            int first = deque.pollFirst();
            if (visited[first] == 0) {
                // 放进结果中
                result[cur ++] = first;
            }
            // 遍历后续节点，并减少度
            for (Integer integer : edges.get(first)) {
                visited[integer] --;
                // 如果度到0了，就放进去
                if (visited[integer] == 0) {
                    deque.addFirst(integer);
                }
            }
        }
        if (cur < numCourses) {
            return new int[0];
        }
        return result;
    }
}
